package leetcode;

import java.util.Arrays;
import java.util.Stack;

import list.LinkedListCreate;
import list.ListNode;

//You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order 
//and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
//
//Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
//Output: 7 -> 0 -> 8

public class AddTwoNumbersLinkedList {
	public static void main(String[] args) {
		int[] array3 = {0,5,6,3,2,9};
		int[] array4 = {1,9,9,9,9,9,9,9,9,9};
		int[] array = {9};
		int[] array2 = {1,9,9,9,9,9,9,9,9,9};
		int[] array5 = {9, 9, 4, 3};
		int[] array6 = {5, 6, 4};
		
		
		ListNode list1 = LinkedListCreate.createList(array);
		ListNode list2 = LinkedListCreate.createList(array2);
		ListNode list3 = LinkedListCreate.createList(array3);
		ListNode list4 = LinkedListCreate.createList(array4);
//		ListNode listResult2 = addTwoNumbers(list3, list4);
//		ListNode listResult = addTwoNumbers(list1, list2);
//		LinkedListCreate.printList(listResult2);
//		LinkedListCreate.printList(listResult);
		ListNode list5 = LinkedListCreate.createList(array5);
		ListNode list6 = LinkedListCreate.createList(array6);
		AddTwoNumbersLinkedList object = new AddTwoNumbersLinkedList();
		ListNode listResult3 = object.addTwoNumbersZhengXu(list5, list6);
		LinkedListCreate.printList(listResult3);
	}
	
	//这尼玛都是啥啊，怎么感觉这个不靠谱啊，竟然是将链表中的数字转换成了long
	public static ListNode addTwoNumbers(ListNode list1, ListNode list2) {
		int[] numbers1 = new int[100];
		int[] numbers2 = new int[100];
		ListNode temp1 = list1;
		ListNode temp2 = list2;
		long number1 = 0;
		long number2 = 0;
		int count1 = 0; // use this to record how much of the node
		int count2 = 0;
		while (temp1 != null) {
			numbers1[count1] = temp1.val;
			count1++;
			temp1 = temp1.next;
		}
		while (temp2 != null) {
			numbers2[count2] = temp2.val;
			count2++;
			temp2 = temp2.next;
		}
		for (int i = count1 - 1; i >= 0; i--) {
            number1 = number1 * 10 + numbers1[i];
		}
		for (int i = count2 - 1; i >= 0; i--) {
			number2 = number2 * 10 + numbers2[i];
		}
		System.out.println("number1: " + number1);
		System.out.println("number2: " + number2);
		long result = number1 + number2;
		if(result == 0){
			return new ListNode(0);
		}
		int[] results = new int[Math.max(count1, count2) + 1];
		int count3 = 0;   //result nodes
		while(result > 0){
			results[count3++] = (int) (result % 10);
			result /= 10;
		}
//		System.out.println("count3: " + count3);
		//由于加法最后可能会进位，所以要进行判断
		if(count3 == results.length){
			return LinkedListCreate.createList(results);
		}else{
			//如果没有进位
			return LinkedListCreate.createList(Arrays.copyOf(results, count3));
		}
	}
	
	
	public ListNode addTwoSum2(ListNode list1, ListNode list2){
		ListNode res = new ListNode(0);
		ListNode head = res;	//head的下一个才指向result的头结点
		int carry = 0, curSum = 0;
		while(list1 != null || list2 != null || carry != 0){
			curSum = (list1 != null ? list1.val : 0) + (list2 != null ? list2.val : 0) + carry;
			carry = curSum / 10;
			res = (res.next = new ListNode(curSum % 10));
			list1 = (list1 == null ? null: list1.next);
			list2 = (list2 == null ? null: list2.next);
		}
		return head.next;
	}
	
	//the others code
	public static ListNode addTwoSum(ListNode l1, ListNode l2){
		ListNode ln1 = l1, ln2 = l2, head = null, node = null;
        int carry = 0, remainder = 0, sum = 0;
        head = node = new ListNode(0);
        
        while(ln1 != null || ln2 != null || carry != 0) {
            sum = (ln1 != null ? ln1.val : 0) + (ln2 != null ? ln2.val : 0) + carry;
            carry = sum / 10;
            remainder = sum % 10;
            node = node.next = new ListNode(remainder);
            ln1 = (ln1 != null ? ln1.next : null);
            ln2 = (ln2 != null ? ln2.next : null);
        }
        return head.next;
	}
	
    public ListNode addTwoNumbersZhengXu(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null){
            return null;
        }
        //if we can't modify the list, then we can use stack
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        Stack<Integer> res = new Stack<Integer>();
        ListNode node1 = l1;
        ListNode node2 = l2;
        while(node1 != null){
            stack1.add(node1.val);
            node1 = node1.next;
        }
        while(node2 != null){
            stack2.add(node2.val);
            node2 = node2.next;
        }
        int carry = 0, curSum = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry == 1){
            curSum = (stack1.isEmpty() ? 0 : stack1.pop()) + (stack2.isEmpty() ? 0 : stack2.pop()) + carry;
			carry = curSum / 10;
			res.add(curSum % 10);
        }
        ListNode head = new ListNode(0);
        ListNode node = head;
        System.out.println(" size: " + res.size());
        while(!res.isEmpty()){
            node.next = new ListNode(res.pop());
            node = node.next;
        }
        return head.next;
    }
}
